package ch02Sort;
//希尔排序
public class Shell extends Sort{
    //和插入排序类似，唯一的不同是他可以交换相邻为h的元素
    //在数组规模比较大并且小元素在右端时该算法可以有效解决插入排序的弊端
    public static void sort(Comparable[] a) {
        int n = a.length;
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = 1; i < n; i++) {
                for (int j = i; j >= h && less(a[j],a[j-h]); j -= h) {
                    exch(a, j, j - h);
                }

            }

            h /= 3;
        }

    }

    public static void main(String[] args) {

        sort(Sort.a);
        System.out.print("现数组：");
        show(Sort.a);
        System.out.print("isSorted？");
        System.out.println(isSorted(Sort.a));

    }
}
